package LeetCode热题HOT100;

public class p38外观数列 {
    public String countAndSay(int n) {
        if (n==0) return null;
        if (n==1) {
            return "1";
        }
        //动态规划
        String[] dp=new String[n+1];
        dp[1]="1";
        dp[2]="11";

        for (int i = 3; i <=n ; i++) {
            String prev=dp[i-1];
            char[] prevChars = prev.toCharArray();
            char curFind=prevChars[0];
            int count=1;
            StringBuilder sb=new StringBuilder();
            for (int j = 1; j <prevChars.length ; j++) {
                if (prevChars[j] != curFind) {
                    sb.append(count);
                    sb.append(curFind);
                    curFind=prevChars[j];
                    count=1;
                }else {
                    count++;
                }
            }

            sb.append(count);
            sb.append(curFind);
            dp[i]=sb.toString();
        }
        return dp[n];
    }
}
